%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Sage Constructions}

Sage is a computer algebra system providing a common mathematical interface
to many common open source computer algebra packages.  The Sage shell is a
customised shell {\tt iPython} to the standard {\tt Python} language.
The design of Sage aims to provide an intuitive, mathematically rigorous
interface to a large code base of algorithms.  Its name is an acronym for
\begin{center}
{\tt Software for Algebra and Geometry Experimentation}.
\end{center}
In this course we use Sage to experiment with cryptographic algorithms and
constructions with a custom cryptosystem package.

\begin{center}
{\large\bf Obtaining Sage}
\end{center}

Sage is a freely available computer algebra system which can be downloaded from
any of the following mirrors:
\begin{enumerate}
\setlength{\itemsep}{0mm}
\item \url{http://sage.math.washington.edu/sage}
\item \url{http://modular.fas.harvard.edu/sage}
\item \url{http://echidna.maths.usyd.edu.au/sage}
\item \url{http://sage.scipy.org/sage}
\item \url{http://cocoa.mathematik.uni-dortmund.de/sage}
\end{enumerate}
\begin{center}

{\large\bf The Sage Shell}
\end{center}

\noindent
To start the Sage shell, just type:
%skip
\begin{verbatim}
> sage
\end{verbatim}
You should see something like:
%skip
\begin{verbatim}
> sage
--------------------------------------------------------
| SAGE Version 1.5.3, Build Date: 2007-01-05           |
| Distributed under the GNU General Public License V2. |
--------------------------------------------------------



sage:
\end{verbatim}

\begin{center}
{\large\bf Entering commands.}
\end{center}

Basic types like integers and rational numbers are built in and can be typed
directly at the command line.
%
\begin{lstlisting}
sage: 1 + 1
2
sage: (2^64+1).factor()
274177 * 67280421310721
sage: 231/23 * 2/55
42/115
\end{lstlisting}
%
(The symbol {\tt sage:} is the prompt and not typed.)
Basic operations such as {\tt +, -, *, /} invoke underlying commands in the
Sage library of functions (with automatically recognition of the types of
the arguments and application the correct algorithm which applies).
More advanced functions like {\tt factor} are also linked into the underlying
code base of Sage.

\begin{center}
{\large\bf Types and Parents}
\end{center}

\noindent
Every object in Sage have a {\tt type} and a {\tt parent}.  The type may be
either a standard Python classes or a class implemented in Sage.
\begin{lstlisting}
sage: x = 2
sage: type(x)
<type 'sage.rings.integer.Integer'>
sage: y = 2/1
sage: type(y)
<type 'sage.rings.rational.Rational'>
sage: z = '2'
sage: type(z)
<type 'str'>
\end{lstlisting} %link

The class of an object determines which functions apply to it.  The printing of
an object does not in general determine the object itself.

Each class of object has special {\it member functions} which apply to it; the
result depends on the function definition.  A member function is called by
typing the object name, a '.', followed by the function name and any arguments
it takes in parentheses.  For instance, the integer $2$ is not a unit in $\Z$,
since there is no element $1/2$ in $\Z$.  In contrast, the element $2$ as a
rational number is a unit.
%link
\begin{lstlisting}
sage: x.is_unit()
False
sage: y.is_unit()
True
\end{lstlisting} %link
An easy way to determine what member functions exist is to type the first few
characters and a TAB to see what functions complete it:
%skip
\begin{lstlisting}
sage: x.is
x.is_nilpotent   x.is_prime       x.is_squarefree  x.is_zero
x.is_one         x.is_square      x.is_unit        x.isqrt
sage: x.is
\end{lstlisting}
To determine what a function does, type (the object, '.', and) the function name, followed
by a ? (and return):
%skip
\begin{lstlisting}
sage: x.is_unit?
Type:           builtin_function_or_method
Base Class:     <type 'builtin_function_or_method'>
String Form:    <built-in method is_unit of sage.rings.integer.Integer object at 0x86676f0>
Namespace:      Interactive
Docstring:

            Returns true if this integer is a unit, i.e., 1 or -1.

            EXAMPLES:
                sage: for n in srange(-2,3):
                          print n, n.is_unit()
                -2 False
                -1 True
                0 False
                1 True
                2 False
\end{lstlisting}
Typing a double question mark {\tt ??} returns the same documentation
string {\it plus} the source code which implements the function in Python.

The parent of an object is itself a object in Sage, which represents the
mathematical structure to which an object belongs:
%link
\begin{lstlisting}
sage: parent(x)
Integer Ring
sage: parent(y)
Rational Field
\end{lstlisting} %link
These parent classes admit their own member functions:
%link
\begin{lstlisting}
sage: ZZ = parent(x)
sage: ZZ.is_field()
False
sage: QQ = parent(y)
sage: QQ.is_field()
True
\end{lstlisting}

\begin{center}
{\large\bf Assignment and output}
\end{center}

As we have seen, the assignment operator is {\tt =}. To print an object in Sage,
just type it at the command line:
\begin{lstlisting}
sage: x = 2
sage: y = 2/1
sage: z = '2'
sage: x
2
sage: y
2
sage: z
'2'
\end{lstlisting} %link
The operator {\tt ==} tests {\it mathematical} equality, which may involve an
evaluation of one object in the parent of the other to carry out the comparison.
%link
\begin{lstlisting}
> x == y
True
> z == y
False
\end{lstlisting}
In the first line above, the integer {\tt x} is interpreted as a rational number
and found to be equal to {\tt y} (and vice versa).

\begin{center}
{\large\bf Booleans and boolean operators}
\end{center}

The boolean truth values {\tt True} and {\tt False} have their own types in Sage
(in fact in Python), which take the special binary boolean operators {\tt and},
{\tt or}, and unary operator {\tt not}.
\begin{lstlisting}
sage: a = True
sage: type(a)
<type 'bool'>
sage: b = False
sage: a and b
False
sage: a or b
True
sage: not a
False
\end{lstlisting}

\begin{center}
{\large\bf Lists, tuples, sets, and dictionaries}
\end{center}

Python (hence Sage) has useful data structures called lists, tuples, and
dictionaries which can be used to collect objects in Sage.
\begin{lstlisting}
sage: type([])
<type 'list'>
sage: type(())
<type 'tuple'>
sage: type({})
<type 'dict'>
\end{lstlisting}
The list and tuple types collects sequences of data which is indexed like strings:
\begin{lstlisting}
sage: s = [ 16, 9, 4, 1, 0, 1, 4, 9, 16 ]
sage: t = ( 16, 9, 4, 1, 0, 1, 4, 9, 16 )
sage: [ s[i] == t[i] for i in range(9) ]
[True, True, True, True, True, True, True, True, True]
\end{lstlisting} %link
Note that all strings, lists, and tuples are indexed from {\tt 0} and {\tt range(n)}
returns the list of elements from {\tt 0} to {\tt 9}:
%link
\begin{lstlisting}
sage: range(9)
[0, 1, 2, 3, 4, 5, 6, 7, 8]
\end{lstlisting} %link
The main distinction is that tuples are {\it immutable}:
%skip
\begin{lstlisting}
sage: t[0] = 4
---------------------------------------------------------------------------
<type 'exceptions.TypeError'>             Traceback (most recent call last)

...

<type 'exceptions.TypeError'>: 'tuple' object does not support item assignment
\end{lstlisting}
while list elements can be reassigned:
%link
\begin{lstlisting}
sage: s[0] = 4
sage: s[8] = 4
sage: s
[4, 9, 4, 1, 0, 1, 4, 9, 4]
\end{lstlisting}
A set in Sage (i.e. Python) represents a mathematical set -- an unordered collection
of objects with each object represented only once.
\begin{lstlisting}
sage: s = set([ 16, 9, 4, 1, 0, 1, 4, 9, 16 ])
sage: s
set([16, 9, 4, 0, 1])
sage: 16 in s
True
sage: len(s) # the cardinality of the set
5
\end{lstlisting}
The set type has very fast hashed lookup, so that membership test is efficient for sets
of large (finite) cardinality.

A dictionary is a useful tool for specifying a lookup table of data indexed by {\it keys}:
\begin{lstlisting}
sage: u = { 0 : 'yes', 1 : 'no', 2 : 'no', 3 : 'yes' }
sage: u[0]
'yes'
sage: u[-1] = 'no'
sage: u[-2] = 'no'
sage: u[-3] = 'yes'
sage: u
{0: 'yes', 1: 'no', 2: 'no', 3: 'yes', -1: 'no', -3: 'yes', -2: 'no'}
sage: u.keys()
[0, 1, 2, 3, -1, -3, -2]
\end{lstlisting}

\begin{center}
{\large\bf Loops and flow control}
\end{center}

Recall that {\tt range(n)} returns the sequence of integers (actually Python {\tt int}'s)
from {\tt 0} up to {\tt n}.  We demonstrate the use of {\tt for} and {\tt if} loops by
printing the elements in {\tt 0,..,12} which are coprime to {\tt 12}:
%skip
\begin{lstlisting}
sage: n = 12
sage: for i in range(n):
....:     if gcd(i,n) == 1:
....:         print i # now hit enter twice
....:
1
5
7
11
\end{lstlisting}
Putting together our use of sets, we demonstrate the use of {\tt if} and {\tt while} loops
to construct the same set of integers in {\tt 0,..,n}:
%skip
\begin{lstlisting}
sage: n = 12
sage: r = euler_phi(n)
sage: i = 1
sage: S = set([i])
sage: while len(S) < r:
....:     i += 1
....:     if GCD(i,n) == 1:
....:         S.add(i) # hit enter twice
....:
sage: S
set([1, 11, 5, 7])
\end{lstlisting}
In each instance the indentation level is crucial to determine the limits of the loops,
which can consist of several lines of commands.

\begin{center}
{\large\bf Python Strings}
\end{center}

\noindent
A useful Python types for this course will be strings, which can be created
by enclosing input in double quotes {\it or} in single quotes.
\begin{lstlisting}
sage: S = 'This\n  is\n    a \n     string'
sage: S
'This\n  is\n    a \n     string'
sage: print S
This
  is
    a
     string
sage: T = "This\n  is\n    a \n     string"
sage: T
'This\n  is\n    a \n     string'
sage: S == T
True
\end{lstlisting}
As seen above, a string can contain newline characters and spaces.  The two characters
{\tt \bs}, {\tt "}, and {\tt '} have special functionality, and must be typed as
{\tt \bs\bs}, {\tt \bs"}, and {\tt \bs'}, respectively (not quite {\tt True}).
The newline string can be created directly by {\tt "\bs{n}"} or carriage return
{\tt "\bs{r}"}.  Strings are like lists of characters, for which {\tt S[i]} gives
access to the {\tt i}-th character of string {\tt S}. The member function {\tt join}
can be used to concatenate strings, but must be applied to a string object!
We demonstrate the use of these operators in the following construction:
\begin{lstlisting}
sage: s = "But Angie, Angie, ain't it time we said good-bye?\n"
sage: t = "With no loving in our souls "
sage: u = "and no money in our coats\n"
sage: v = "You can't say we're satisfied\n\n"
sage: w = "...they can't say we never tried"
sage: null = ''
sage: angie = null.join([s,t,u,v,w])
sage: print angie
But Angie, Angie, ain't it time we said good-bye?
With no loving in our souls and no money in our coats
You can't say we're satisfied
<BLANKLINE>
...they can't say we never tried
\end{lstlisting} %link
and subsequently we cat deconstruct and reassemble our strings:
%link
\begin{lstlisting}
sage: I = [55+i for i in range(3)] + [124 + i for i in range(6)]
sage: I += [4,143,138,164,56,55]
sage: print null.join([ angie[i] for i in I ])
no satisfAction
\end{lstlisting}
